home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / b_queue.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.4 KB  |  49 lines
  1. {\magonebf 3.6 Bounded Queues (b\_queue) }
  2.  
  3. \decl b\_queue E
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $Q$ of the paramerized data type \name\ is a queue
  8. (see section 2.4) of bounded size. 
  9.  
  10. \bigskip
  11. {\bf 2. Creation}
  12.  
  13. \create Q (n)   
  14.  
  15. creates an instance \var\ of type \name\ that can hold up to $n$ elements.
  16. \var\ is initialized with the empty queue.
  17.  
  18.  
  19. \bigskip
  20. {\bf 3. Operations}
  21. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  22. \+\op E     top    {}       
  23.                             { returns the front element of \var}
  24. \+\nop                      { \precond $Q$ is not empty.}
  25. \smallskip
  26. \+\op E     pop    {}       
  27.                             { deletes and returns the front element of \var}
  28. \+\nop                      { \precond $Q$ is not empty.}
  29. \smallskip
  30. \+\op void  append {E\ x}   
  31.                             { appends $x$ to the rear end of \var}
  32. \+\nop                      { \precond $Q$.size()$ < n$.}
  33. \smallskip
  34. \+\op void  clear  {}       
  35.                             { makes \var\ the empty queue.}
  36. \smallskip
  37. \+\op int   size   {}       
  38.                             { returns the size of \var.}
  39. \smallskip
  40. \+\op bool  empty  {}       
  41.                             { returns true if \var\ is empty, false otherwise.}
  42.  
  43. \bigskip
  44. {\bf 4. Implementation}
  45.  
  46. Bounded Queues are implemented by circular arrays. All operations take 
  47. time $O(1)$. The space requirement is $O(n)$.
  48.  
  49.